package br.ufrn.ciencomp.filaprioridade;

import java.io.File;
import java.io.IOException;
import java.util.Scanner;

public class FilaPrioridade {
	//Fila
	public Tipo tipo;
	public int tamanho;
	public enum Tipo {MIN, MAX};
	public Item[] heap;
	
	public FilaPrioridade(String tipo) {
		if(tipo.equals("MAX"))
			this.tipo = Tipo.MAX;
		else if(tipo.equals("MIN"))
			this.tipo = Tipo.MIN;
		
		heap = new Item[1000];
		tamanho = 0;
	}
	
	private void subir(int n) {
		if(tipo == Tipo.MAX) {
			while(n > 0) {
				if(n/2 != 0 && heap[n].prioridade > heap[n/2].prioridade) {
					Item aux = heap[n];
					heap[n] = heap[n/2];
					heap[n/2] = aux;
					
					n /= 2;
				} else {
					break;
				}
			}
		} else if(tipo == Tipo.MIN) {
			while(n > 0) {
				if(n/2 != 0 && heap[n].prioridade < heap[n/2].prioridade) {
					Item aux = heap[n];
					heap[n] = heap[n/2];
					heap[n/2] = aux;
					
					n /= 2;
				} else {
					break;
				}
			}
		}
	}
	
	public void insert(int valor, int prioridade) {
		for(int i = 1; i <= tamanho; i++) {
			if(heap[i].valor == valor) {
				System.out.println("notinserted");
				return;
			}
		}
		
		tamanho++;
		Item novo = new Item(valor, prioridade);
		heap[tamanho] = novo;
		
		subir(tamanho);
		
		System.out.println("-");
	}
	
	private void descer(int n) {
		if(tipo == Tipo.MAX) {
			while(true) {
				int maior = 0;
				
				if(n * 2 <= tamanho) {
					if(heap[n].prioridade < heap[n*2].prioridade) {
						maior = n*2;
					}
				}
				
				if((n * 2) + 1 <= tamanho) {
					if(heap[n].prioridade < heap[(n*2)+1].prioridade) {
						maior = (n*2)+1;
					}
				}
				
				if(maior == 0) {
					break;
				} else {
					Item aux = heap[n];
					heap[n] = heap[maior];
					heap[maior] = aux;
					
					n = maior;
				}
			}
		} else if(tipo == Tipo.MIN) {
			while(true) {
				int menor = 0;
				
				if(n * 2 <= tamanho) {
					if(heap[n].prioridade > heap[n*2].prioridade) {
						menor = n*2;
					}
				}
				
				if((n * 2) + 1 <= tamanho) {
					if(heap[n].prioridade > heap[(n*2)+1].prioridade) {
						menor = (n*2)+1;
					}
				}
				
				if(menor == 0) {
					break;
				} else {
					Item aux = heap[n];
					heap[n] = heap[menor];
					heap[menor] = aux;
					
					n = menor;
				}
			}
		}
	}
	
	public void extract() {
		if(tamanho >= 1) {
			Item topo = heap[1];
			
			Item aux = heap[1];
			heap[1] = heap[tamanho];
			heap[tamanho] = aux;
			
			tamanho--;
			
			descer(1);
			
			System.out.println(topo.valor + " " + topo.prioridade);
		} else {
			System.out.println("empty");
		}
	}
	
	public void decrease(int valor, int prioridade) {
		int i = 1;
		System.out.println("Quero: " + valor);
		while(i <= tamanho) {
			System.out.print(heap[i].valor + " ");
			i++;
		}
		
		i = 1;
		while(heap[i].valor != valor) {
			i++;
		}
		if(prioridade < heap[i].prioridade) {
			heap[i].prioridade = prioridade;
			subir(i);
			System.out.println("-");
		} else {
			System.out.println("notupdated");
		}
	}
	
	public void increase(int valor, int prioridade) {
	}

	public static void main(String args[]) {
		try {
			Scanner scanner = new Scanner(new File("streams/filaprioridade1.in"));
			
			FilaPrioridade f = new FilaPrioridade(scanner.next());
			System.out.println("-");
			
			while(scanner.hasNext()) {
				String instrucao = scanner.next();
				if(instrucao.startsWith("insert")) {
					f.insert(scanner.nextInt(), scanner.nextInt());
				} else if(instrucao.equals("extract")) {
					f.extract();
				} else if(instrucao.equals("increase")) {
					f.increase(scanner.nextInt(), scanner.nextInt());
				} else if(instrucao.equals("decrease")) {
					f.decrease(scanner.nextInt(), scanner.nextInt());
				}
			}
		} catch(IOException e) {
			e.printStackTrace();
		}
	}
}
